#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
    
};

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* head = new ListNode(-1);
    ListNode* pre = head;
    int carry = 0;
    while (l1 || l2 || carry)
    {
        int sum = 0;
        if (l1)
        {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2)
        {
            sum += l2->val;
            l2 = l2->next;
        }
        pre->next = new ListNode((carry + sum) % 10);
        pre = pre->next;
        carry = (carry + sum) / 10;
    }
    return head->next;
}

int maxDepth(string s) {
    int ret = 0, cnt = 0;
    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == '(') ++cnt;
        if (s[i] == ')') --cnt;
        ret = max(ret, cnt);
    }
    return ret;
}

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

bool evaluateTree(TreeNode* root) {
    if (root->left == nullptr) return root->val == 0 ? false : true;
    return root->val == 2 ? evaluateTree(root->left) || evaluateTree(root->right) :
        evaluateTree(root->left) && evaluateTree(root->right);
}

string minWindow(string s, string t)
{
    int hash1[128] = { 0 }, hash2[128] = { 0 };
    int kinds = 0;
    for (auto ch : t)
    {
        if (hash1[ch]++ == 0) ++kinds;
    }
    int len = INT_MAX, start = -1, cnt = 0;
    for (int left = 0, right = 0; right < s.size(); ++right)
    {
        char in = s[right];
        if (++hash2[in] == hash1[in]) ++cnt;
        while (cnt >= kinds)
        {
            if (len > right - left + 1)
            {
                start = left;
                len = right - left + 1;
            }
            char out = s[left++];
            if (hash2[out]-- == hash1[out]) --cnt;
        }
    }
    return start == -1 ? "" : s.substr(start, len);
}